class Solution(object):
    def numberOfUniqueGoodSubsequences(self, binary):
        n = len(binary)
        d = {'0':-1, '1':-1}
        p = [0] * n
        prefix = [0] * n
        for i in range(n):
            p[i] = d[binary[i]]
            d[binary[i]] = i
            if i == 0:
                prefix[i] = int(binary[i] == '1')
            else:
                prefix[i] = prefix[i - 1] + int(binary[i] == '1')
        base = 10 ** 9 + 7
        ans = [0] * n
        for i in range(n):
            if p[i] == -1:
                if i == 0:
                    ans[i] = 1
                else:
                    if binary[i] == '0':
                        ans[i] = 2 * ans[i - 1] + 1
                    else:
                        ans[i] = ans[i - 1] + 1
            else:
                if binary[i] == '1':
                    if p[i] == 0:
                        if prefix[i] < i + 1:
                            ans[i] = 2 * ans[i - 1] - 1
                        else:
                            ans[i] = 2 * ans[i - 1]
                    else:
                        last_i = p[i]
                        ans[i] = (2 * ans[i - 1] - ans[last_i - 1]) % base
                        if prefix[last_i - 1] == last_i and prefix[i] < i + 1:
                            ans[i] = (ans[i] - 1) % base
                else:
                    if p[i] == 0:
                        ans[i] = 2 * ans[i - 1] - 1
                    else:
                        last_i = p[i]
                        ans[i] = (2 * ans[i - 1] - ans[last_i - 1]) % base
                        if p[last_i] == -1:
                            ans[i] = (ans[i] - 1) % base
        return ans[-1]


data = Solution()
binary = "10101"
print(data.numberOfUniqueGoodSubsequences(binary))
binary = "1110001"
print(data.numberOfUniqueGoodSubsequences(binary))